11.5 Complexity

131

believed)? No. Do we have more cell types than other organisms? Yes, and the mouse

has more than the fly, but then complexity becomes merely a synonym for variety.

Or does it reflect what we can do? Man alone can create poems, theories, musical

compositions, paintings, and so forth. However, although one could perhaps compare

the complexity of different human beings on that basis, it would be useless for the

rest of the living world. Is complexity good or bad? A complex theory that nobody

apart from its inventor can understand might be impressive, but not very useful. On

the other hand, we have the notion, again rather intuitive, that a complex organism is

more adaptable than a simple one, because it has more possibilities for action; hence,

it can better survive in a changing environment. ¹⁰

Other pertinent questions are whether complexity is an absolute attribute of an

object, or does it depend on the level of detail with which one describes it (in other

words, how its description is encoded—an important consideration if one is going

to extract a number to quantify complexity)? Every writer on the subject seems to

introduce his own particular measure of complexity, with a corresponding special

name—what do these different measures have in common? Do printed copies of a

Shakespeare play have the same complexity as the original manuscript? Does the

fiftieth edition have less complexity than the first?

The antonym of complexity is simplicity; the antonym of randomness is regularity.

A highly regular pattern is also simple. Does this, then, suggest that complexity is

a synonym for randomness?

An important advance was Kolmogorov’s notion of algorithmic complexity (also

called algorithmic information content or AIC) as a criterion for randomness. As we

have seen near the beginning of this chapter (Footnote 4), the AIC, upper K left parenthesis s right parenthesisK(s), of a string

ss is the length of the smallest program (running on a universal computing machine)

able to print out ss. Henceforth we shall mainly consider the complexity of strings

(objects can, of course, be encoded as strings). If there are no regularities,upper K left parenthesis s right parenthesisK(s) will

have its maximum possible value, which will be roughly equal to the length of the

string; no compression is possible and the string has to be printed out verbatim. ¹¹

Hence,

Kmax = |s| .

(11.26)

Any regularities (i.e., constraints in the choice of successive symbols) will diminish

the value of upper KK. We call upper K Subscript normal m normal a normal xKmax the unconditional complexity; it is actually a measure

of regularity.

10 If this is so, it then seems rather strange that so much ingenuity is expended by presumably

complex people to make their environments more uniform and unchanging, in which case they will

tend to lose their competitive advantage.

11 Many considerations of complexity may be reduced to the problem of printing out a number.

Thus, the complexity of a protein structure is related to the number specifying the positions of the

atoms, or dihedral angles of the peptide groups, which is equivalent to selecting one from a list of

all possible conformations; the difficulty of doing that is roughly the same as that of printing out

the largest number in that list.